import java.lang.reflect.Array;
import java.util.*;

public class MinStack {

    //设计循环队列

    class MyCircularQueue {
        public int[] elem;
        public int first;
        public int last;

        public MyCircularQueue(int k) {
            elem = new int[k];
        }

        public boolean enQueue(int value) {
            if(isFull()){
                return false;
            }
            elem[last] = value;
            last = (last+1)%elem.length;
            return true;
        }

        public boolean deQueue() {
            if(isEmpty()){
                return false;
            }
            first = (first+1)%elem.length;
            return true;
        }

        public int Front() {
            if(isEmpty()){
                return -1;
            }
            return elem[first];
        }

        public int Rear() {
            if(isEmpty()){
                return -1;
            }
            int index = (last == 0) ? elem.length-1 : last-1;
            return elem[index];
        }

        public boolean isEmpty() {
            return first == last;
        }

        public boolean isFull() {
            return (last+1)%elem.length == first;
        }
    }

    //用栈实现队列

    class MyQueue {
        public ArrayDeque<Integer> s1;
        public ArrayDeque<Integer> s2;

        public MyQueue() {
            s1 = new ArrayDeque<>();
            s2 = new ArrayDeque<>();
        }

        public void push(int x) {
            s1.push(x);
        }

        public int pop() {
            if(empty()){
                return -1;
            }
            if(s2.isEmpty()) {
                while (!s1.isEmpty()) {
                    s2.push(s1.pop());
                }
            }
            return s2.pop();
        }

        public int peek() {
            if(empty()){
                return -1;
            }
            if(s2.isEmpty()) {
                while (!s1.isEmpty()) {
                    s2.push(s1.pop());
                }
            }
            return s2.peek();
        }

        public boolean empty() {
//            if(s1.isEmpty() && s1.isEmpty()){
//                return true;
//            }
//            return false;
            return s1.isEmpty() && s2.isEmpty();
        }
    }

    //用队列实现栈

    class MyStack {
        public Queue<Integer> queue1;
        public Queue<Integer> queue2;

        public MyStack() {
            queue1 = new LinkedList<>();
            queue2 = new LinkedList<>();
        }

        public void push(int x) {
            if(empty()){
                queue1.offer(x);
                return;
            }
            if(!queue1.isEmpty()){
                queue1.offer(x);
            }else{
                queue2.offer(x);
            }
        }

        public int pop() {
            if(empty()){
                return -1;
            }
            if(!queue1.isEmpty()){
                int size = queue1.size();
                for (int i = 0; i < size-1; i++) {
                    queue2.offer(queue1.poll());
                }
                return queue1.poll();
            }else{
                int size = queue2.size();
                for (int i = 0; i < size-1; i++) {
                    queue1.offer(queue2.poll());
                }
                return queue2.poll();
            }
        }

        public int top() {
            if(empty()){
                return -1;
            }
            if(!queue1.isEmpty()){
                int size = queue1.size();
                int ret = -1;
                for (int i = 0; i < size; i++) {
                    ret = queue1.poll();
                    queue2.offer(ret);
                }
                return ret;
            }else{
                int size = queue2.size();
                int ret = -1;
                for (int i = 0; i < size; i++) {
                    ret = queue2.poll();
                    queue1.offer(ret);
                }
                return ret;
            }
        }

        public boolean empty() {
            if(queue1.isEmpty() && queue2.isEmpty())
            {
                return true;
            }
            return false;
        }
    }

   // 栈的压入、弹出序列
   public boolean IsPopOrder (int[] pushV, int[] popV) {
       // write code here
       Stack<Integer> stack = new Stack<>();
       int j = 0;
       for (int i = 0; i < pushV.length; i++) {
           stack.push(pushV[i]);
           while(j < popV.length && !stack.empty() && stack.peek() == popV[j]){
               stack.pop();
               j++;
           }
       }
       return stack.empty();
   }

//有效的括号
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            //左括号入栈
            if(ch == '(' || ch == '[' || ch == '{'){
                stack.push(ch);
            }else{
                //遇到右括号
                if(stack.empty()){
                    return false;
                }else{
                    //当前左括号 与 右括号 是否匹配
                    //如果不匹配，则直接return;
                    char chL = stack.peek();
                    if(chL == '(' && ch == ')' || chL == '[' && ch == ']'
                    || chL == '{' && ch == '}'){
                        stack.pop();
                    }else{
                        return false;
                    }
                }
            }
        }
        return stack.empty();
    }


    //最小栈元素
    Stack<Integer> stack;
    Stack<Integer> minstack;

    public MinStack() {
     stack = new Stack<>();
     minstack = new Stack<>();
     //min栈存放最小元素，若val比当前栈顶元素小则入栈；
    }

    public void push(int val) {
        stack.push(val);
        if(minstack.empty()){
            minstack.push(val);
        }else{
            Integer peekval = minstack.peek();
            if(val <= peekval){
                minstack.push(val);
            }
        }
    }

    public void pop() {
        if(minstack.empty()){
            return;
        }
        int popval = stack.pop();
        if(popval == minstack.peek()){
            minstack.pop();
        }
    }

    public int top() {
        if(stack.empty()){
            return -1;
        }
        return stack.peek();
    }

    public int getMin() {
        if(minstack.empty()){
            return -1;
        }
        return minstack.peek();
    }
}
